Public key cryptography with the RSA cryptosystem involves generating a pair of keys that serve to encrypt or decrypt confidential communications sent over the Internet: a private key that a party keeps as a secret, and a public key that the party publishes on the Internet. For example, suppose that a first party wishes to ensure that a fraudster has not tampered with a confidential message sent to him from a second party. The second party encrypts the message with the public key before sending the message; the first party subsequently decrypts the encrypted message with the private key.
The generation of certain pairs of keys involves generating a pair of prime numbers, a prime number being a number that has no factors except unity and itself. The private key includes knowledge of the prime numbers, while the public key includes the product of the pair. Communications encrypted with such a public key are reasonably secure when the prime numbers are sufficiently large (typically more than 512 bits), because there does not exist an efficient algorithm for performing a prime factorization of an arbitrary large integer. That is, it is impractical to attempt to ascertain a private key, which includes knowledge of the prime factors of a large integer, from a public key, which includes the large integer, also known as the modulus of the public key.
A conventional key pair generator produces prime numbers using a random number generator (RNG). Along these lines, the key pair generator employs the following process in obtaining a prime number: i) obtain a random seed from some random process (e.g., a physical process in physical hardware that exhibits randomness); ii) input the random seed into the RNG to produce an integer output; and iii) find a prime factor near this integer through a search technique. The key pair generator finds the other prime factor by repeating the above process.